/*
https://leetcode-cn.com/problems/valid-permutations-for-di-sequence/solution/di-xu-lie-de-you-xiao-pai-lie-by-leetcode/
 */
public class Solution903 {
    public int numPermsDISequence(String s) {
        int n=s.length();
        int m=1000000007;
        int[][] f=new int[n+1][n+1];
        f[0][0]=1;
        for (int i=1;i<=n;i++){
            for (int j=0;j<=i;j++){
                if (s.charAt(i-1)=='I'){
                    for (int k=0;k<j;k++){
                        f[i][j]=(f[i][j]+f[i-1][k])%m;
                    }
                }else{
                    for (int k=j;k<i;k++){
                        f[i][j]=(f[i][j]+f[i-1][k])%m;
                    }
                }
            }
        }
        int ans=0;
        for (int i=0;i<=n;i++){
            ans=(ans+f[n][i])%m;
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution903().numPermsDISequence("DID"));
    }
}
